
/**
 * 
 * 关联子串
 * 
 * 题目描述

给定两个字符串str1和str2，如果字符串str1中的字符，经过排列组合后的字符串中，只要有一个字符串是str2的子串，则认为str1是str2的关联子串。

若str1是str2的关联子串，请返回子串在str2的起始位置；

若不是关联子串，则返回-1。

输入描述
输入两个字符串，分别为题目中描述的str1、str2。

输出描述
若str1是str2的关联子串，请返回子串在str2的起始位置；

若不是关联子串，则返回-1。

若str2中有多个str1的组合子串，请返回最小的起始位置。

备注
输入的字符串只包含小写字母；
两个字符串的长度范围[1, 100000]之间；
用例
输入	abc efghicbaiii
输出	5
说明	str2包含str1的一种排列组合（"cab")，此组合在str2的字符串起始位置为5（从0开始计数）
输入	abc efghiccaiii
输出	-1
说明	“abc”字符串中三个字母的各种组合（abc、acb、bac、bca、cab、cba），str2中均不包含，因此返回-1

 */

import java.util.Scanner;

/**
  * 题目解析
本题看上去是要求解全排列，但是题目描述数量级为：两个字符串的长度范围[1, 100000]之间；

因此str1的全排列肯定会超时。

本题可以使用尺取法来求解，尺取法其实就是高级一点的滑动窗口，常用于解决最小覆盖子串问题，比如LeetCode - 76 最小覆盖子串_伏城之外的博客-CSDN博客

大家可以认真看下上面这个博客，对尺取法有个大致了解。

尺取法，通常是有一个子串str1，和一个父串str2，我们需要在父串str2中找到包含str1子串所有字符的目标串target，不在意字符顺序。

解决方案很固定：

预处理动作：

统计出子串str1中各字符的数量，记录到count中，这里的count容器通常选择128长度的数组，因为字符串中的字符通常都是ASCII码表的字符，而ASCII码只有128个，因此选择128长度的数组就可以涵盖到所有字符。
定义一个total变量，来记录str1字符的总数（即str1的长度）
滑窗动作：

初始滑窗，即父串str2的0~str1.length-1范围的滑窗。此时滑窗只有新增字符的过程，即滑窗左边界保持在0，而滑窗右边界从0运动到str1.length-1位置。
后续滑窗，即父串str2的 i ~ i + str1.length - 1，其中 i >= 1，每次滑窗整体向右移动一格，即相较于上一个滑窗，会失去 str2[i-1]字符，以及新增 str2[i + str1.length - 1] 字符。
滑窗的意义：

滑窗其实就是一个str2的子串，我们可以基于滑窗来统计滑窗内子串各字符的数量，如果滑窗内各字符的数量与str1各字符数量一致，则说明滑窗内子串就是一个目标子串
滑窗处理新增字符：

当滑窗新增一个字符c时，我们应该count[c] -= 1，表示滑窗子串和str1的差别缩小了，此时total是否也需要-=1吗？total是str1的字符总数，此时需要细化讨论
如果字符c不是str1内的字符，则total不需要-=1
如果字符c是str1内的字符，此时又需要细化讨论，字符c虽然是str1内的字符，但是滑窗内c字符的数量完全有可能超过str1内的字符数量，即滑窗内存在多余的字符c，那么此时滑窗新增了一个c，并不会缩小和str1的差距，即total不需要-=1。
那么此时就需要搞清楚，如何判断滑窗内字符c是否是str1的字符？以及是str1字符的情况下，是否为超标字符？
上面两个判断，可以用一句话实现：count[c] > 0
如果滑窗新增的字符c不是str1字符，则必然count[c] <= 0
如果滑窗新增的字符c是str1字符，但是超标了，则经过count[c]--动作，超过的c字符，必然count[c] <= 0
滑窗处理移除字符：

当滑窗移除一个字符c是，我们应该count[c]++，表示滑窗子串和str1的差别扩大了，此时total是否也需要+=1吗？total是str1的字符总数，此时需要细化讨论：
如果字符c不是str1内的字符，则total不需要+=1
如果字符c是str1内的字符，此时又需要细化讨论，字符c虽然是str1内的字符，但是滑窗内c字符的数量完全有可能超过str1内的字符数量，即滑窗内存在多余的字符c，那么此时滑窗移除一个c，并不会扩大和str1的差距，即不需要total+=1
那么此时就需要搞清楚，如何判断滑窗内字符c是否是str1的字符？以及是str1字符的情况下，是否为超标字符？
上面两个判断，可以用一句话实现：count[c] >= 0
如果滑窗移除的字符c不是str1字符，则移除之前必然count[c] < 0
如果滑窗移除的字符c是str1字符，但是超标了，则移除之前必然count[c] < 0
  */
public class 关联子串 {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
 
        String str1 = sc.next();
        String str2 = sc.next();
    
        System.out.println(getResult(str1, str2));
  }
 
  public static int getResult(String str1, String str2) {
    // count用于统计str1中各字符的数量
    int[] count = new int[128];
    for (int i = 0; i < str1.length(); i++) {
      char c = str1.charAt(i);
      count[c]++;
    }
 
    // total统计str1总共字符个数
    int total = str1.length();
 
    // 初始滑窗，滑窗范围内容，就是一个子串
    for (int i = 0; i < str1.length(); i++) {
      // 滑窗子串新增的字符
      char add = str2.charAt(i);
 
      // 如果新增字符是str1的字符，即count[add] > 0时，则说明滑窗子串已找到一个目标字符，此时剩余add字符数量count[add]--,剩余目标字符总数total--
      if (count[add]-- > 0) {
        total--;
      }
    }
 
    // 如果total == 0，则说明滑窗内所有字符都是str1内的字符，由于限定了滑窗的长度就是str1的长度，因此滑窗内字符和str1完全匹配
    if (total == 0) return 0;
 
    // 下一个滑窗范围是 i ~ i + str1.length() - 1
    for (int i = 1; i + str1.length() - 1 < str2.length(); i++) {
      // 相较于上一个滑窗失去的字符remove
      char remove = str2.charAt(i - 1);
      // 相较于上一个滑窗新增的字符add
      char add = str2.charAt(i + str1.length() - 1);
 
      // 本轮滑窗remove字符，在上一轮是被add的字符，我们假设此字符为c，此时可以分两种情况讨论：
      // 1、c是str1的字符，则初始统计时count[c]>0，上一轮滑窗加入c字符，则count[c]--，此轮count[c]是有可能>=0或者<0的，
      //    1.1、如果本轮count[c]>=0，则说明上轮滑窗并没有找到所有的c字符，因此本轮移除的c字符可以还原total数量
      //
      // 1.2、如果本轮count[c]<0，这说明上轮滑窗内的c字符超标了，即c字符是目标字符，但是滑窗内包含的c字符数量超过了str1中c字符的数量，因此本轮移除c字符是超标部分，不会还原total
      // 2、c不是str1的字符，则初始统计时count[c]==0，上一轮滑窗加入c字符，则count[c]--，此轮必然count[c]<0，因此c字符的移除，并不会还原total
      if (count[remove]++ >= 0) {
        total++;
      }
 
      if (count[add]-- > 0) {
        total--;
      }
 
      if (total == 0) {
        return i;
      }
    }
 
    return -1;
  }
}
